package com.mango.algorithm.tree.binary;

import com.mango.data.structure.binarytree.linknode.TreeNode;

/**
 * 判断满二叉树：节点个数 = 2^最大深度 - 1
 * @Author: mango
 * @Date: 2022/4/14 10:00 下午
 */
public class FullTree {
    public boolean isFullTree(TreeNode root) {
        FullInfo info = process(root);
        return info.nodeCount == Math.pow(2,info.height) - 1;
    }

    public FullInfo process(TreeNode node){
        if(node == null){
            return new FullInfo(0,0);
        }
        FullInfo left = process(node.left);
        FullInfo right = process(node.right);
        // 高度 = 左树或者右树较高的高度 + 当前节点高度1
        int height = Math.max(left.height,right.height) + 1;
        // 节点数 = 左树节点数 + 右树节点数 + 当前节点1
        int nodeCount = left.nodeCount + right.nodeCount + 1;

        return new FullInfo(height,nodeCount);
    }
}

class FullInfo{
    public int height;
    public int nodeCount;

    public FullInfo(int height, int nodeCount) {
        this.height = height;
        this.nodeCount = nodeCount;
    }
}
